﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BaseArith {
    public static class Sortor {
        static void SelectSort(int[] data) {
            var count = data.Length;
            var min = 0;
            for (int i = 0 ; i < count - 1 ; i++) {
                min = i;
                for (int j = i + 1 ; j < count ; j++) {
                    if (data[j] < data[min]) {
                        min = j;
                    }
                }
                var temp = data[min];
                data[min] = data[i];
                data[i] = temp;
            }
        }
        static void BubbleSort(int[] data) {
            var count = data.Length;
            for (int j = 0 ; j < count ; j++) {
                for (int i = count - 1 ; i >= 0 ; i--) {
                    if (data[j] < data[i]) {
                        var temp = data[j];
                        data[j] = data[i];
                        data[i] = temp;
                    }
                }
            }
        }
        static void InsertSort(int[] data) {
            var count = data.Length;
            for (int i = 1 ; i < count ; i++) {
                var t = data[i];
                var j = i;
                while (j > 0 && data[j - 1] > t) {
                    data[j] = data[--j];
                }
                data[j] = t;
            }

        }
        #region quicksourt
        static void QuickSort(int[] data) {
            QuickSort(data,0,data.Length - 1);
        }

        private static void QuickSort(int[] numbers,int left,int right) {
            if (left < right) {
                int middle = numbers[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true) {
                    while (numbers[++i] < middle) ;

                    while (numbers[--j] > middle) ;

                    if (i >= j)
                        break;

                    Swap(numbers,i,j);
                }

                QuickSort(numbers,left,i - 1);
                QuickSort(numbers,j + 1,right);
            }
        }

        private static void Swap(int[] numbers,int i,int j) {
            int number = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = number;
        }
        #endregion
        /// <summary>
        /// 奇偶排序
        /// </summary>
        /// <param name="data"></param>
        static void OddEvenSort(int[] data) {
            var sorted = false;
            var count = data.Length;
            while (!sorted) {
                sorted = true;
                for (var i = 1 ; i < count - 1 ; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data,i,i + 1);
                        sorted = false;
                    }
                }
                for (var i = 0 ; i < count - 1 ; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data,i,i + 1);
                        sorted = false;
                    }
                }
            }

        }
        /// <summary>
        /// 鸡尾酒排序
        /// </summary>
        /// <param name="data"></param>
        static void CocktailSort(int[] data) { // the first element of list has index 0
            var bottom = 0;
            var top = data.Length - 1;
            var swapped = true;
            while (swapped == true) {
                // if no elements have been swapped, then the list is sorted
                swapped = false;
                for (int i = bottom ; i < top ; i = i + 1) {
                    if (data[i] > data[i + 1]) {
                        // test whether the two elements are in the correct order
                        Swap(data,i,i + 1); // let the two elements change places
                        swapped = true;
                    }
                }
                // decreases top the because the element with the largest value in the unsorted
                // part of the list is now on the position top 
                top = top - 1;
                for (int i = top ; i > bottom ; i = i - 1) {
                    if (data[i] < data[i - 1]) {
                        Swap(data,i,i - 1);
                        swapped = true;
                    }
                }
                // increases bottom because the element with the smallest value in the unsorted 
                // part of the list is now on the position bottom 
                bottom = bottom + 1;
            }
        }
        //

        static void SelectSort(float[] data) {
            var count = data.Length;
            var min = 0;
            for (int i = 0 ; i < count - 1 ; i++) {
                min = i;
                for (int j = i + 1 ; j < count ; j++) {
                    if (data[j] < data[min]) {
                        min = j;
                    }
                }
                var temp = data[min];
                data[min] = data[i];
                data[i] = temp;
            }
        }
        static void BubbleSort(float[] data) {
            var count = data.Length;
            for (int j = 0 ; j < count ; j++) {
                for (int i = count - 1 ; i >= 0 ; i--) {
                    if (data[j] < data[i]) {
                        var temp = data[j];
                        data[j] = data[i];
                        data[i] = temp;
                    }
                }
            }
        }
        static void InsertSort(float[] data) {
            var count = data.Length;
            for (int i = 1 ; i < count ; i++) {
                var t = data[i];
                var j = i;
                while (j > 0 && data[j - 1] > t) {
                    data[j] = data[--j];
                }
                data[j] = t;
            }

        }
        #region quicksourt
        static void QuickSort(float[] data) {
            QuickSort(data,0,data.Length - 1);
        }

        private static void QuickSort(float[] data,int left,int right) {
            if (left < right) {
                var middle = data[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true) {
                    while (data[++i] < middle) ;

                    while (data[--j] > middle) ;

                    if (i >= j)
                        break;

                    Swap(data,i,j);
                }

                QuickSort(data,left,i - 1);
                QuickSort(data,j + 1,right);
            }
        }

        private static void Swap(float[] numbers,int i,int j) {
            var number = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = number;
        }
        #endregion
        /// <summary>
        /// 奇偶排序
        /// </summary>
        /// <param name="data"></param>
        static void OddEvenSort(float[] data) {
            var sorted = false;
            var count = data.Length;
            while (!sorted) {
                sorted = true;
                for (var i = 1 ; i < count - 1 ; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data,i,i + 1);
                        sorted = false;
                    }
                }
                for (var i = 0 ; i < count - 1 ; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data,i,i + 1);
                        sorted = false;
                    }
                }
            }

        }
        /// <summary>
        /// 鸡尾酒排序
        /// </summary>
        /// <param name="list"></param>
        static void CocktailSort(float[] list) { // the first element of list has index 0
            var bottom = 0;
            var top = list.Length - 1;
            var swapped = true;
            while (swapped == true) {
                // if no elements have been swapped, then the list is sorted
                swapped = false;
                for (int i = bottom ; i < top ; i = i + 1) {
                    if (list[i] > list[i + 1]) {
                        // test whether the two elements are in the correct order
                        Swap(list,i,i + 1); // let the two elements change places
                        swapped = true;
                    }
                }
                // decreases top the because the element with the largest value in the unsorted
                // part of the list is now on the position top 
                top = top - 1;
                for (int i = top ; i > bottom ; i = i - 1) {
                    if (list[i] < list[i - 1]) {
                        Swap(list,i,i - 1);
                        swapped = true;
                    }
                }
                // increases bottom because the element with the smallest value in the unsorted 
                // part of the list is now on the position bottom 
                bottom = bottom + 1;
            }
        }

        static void SelectSort(double[] data) {
            var count = data.Length;
            var min = 0;
            for (int i = 0 ; i < count - 1 ; i++) {
                min = i;
                for (int j = i + 1 ; j < count ; j++) {
                    if (data[j] < data[min]) {
                        min = j;
                    }
                }
                var temp = data[min];
                data[min] = data[i];
                data[i] = temp;
            }
        }
        static void BubbleSort(double[] data) {
            var count = data.Length;
            for (int j = 0 ; j < count ; j++) {
                for (int i = count - 1 ; i >= 0 ; i--) {
                    if (data[j] < data[i]) {
                        var temp = data[j];
                        data[j] = data[i];
                        data[i] = temp;
                    }
                }
            }
        }
        static void InsertSort(double[] data) {
            var count = data.Length;
            for (int i = 1 ; i < count ; i++) {
                var t = data[i];
                var j = i;
                while (j > 0 && data[j - 1] > t) {
                    data[j] = data[--j];
                }
                data[j] = t;
            }

        }
        #region quicksourt
        static void QuickSort(double[] data) {
            QuickSort(data,0,data.Length - 1);
        }

        private static void QuickSort(double[] data,int left,int right) {
            if (left < right) {
                var middle = data[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true) {
                    while (data[++i] < middle) ;

                    while (data[--j] > middle) ;

                    if (i >= j)
                        break;

                    Swap(data,i,j);
                }

                QuickSort(data,left,i - 1);
                QuickSort(data,j + 1,right);
            }
        }

        private static void Swap(double[] numbers,int i,int j) {
            var number = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = number;
        }
        #endregion
        /// <summary>
        /// 奇偶排序
        /// </summary>
        /// <param name="data"></param>
        static void OddEvenSort(double[] data) {
            var sorted = false;
            var count = data.Length;
            while (!sorted) {
                sorted = true;
                for (var i = 1 ; i < count - 1 ; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data,i,i + 1);
                        sorted = false;
                    }
                }
                for (var i = 0 ; i < count - 1 ; i += 2) {
                    if (data[i] > data[i + 1]) {
                        Swap(data,i,i + 1);
                        sorted = false;
                    }
                }
            }

        }
        /// <summary>
        /// 鸡尾酒排序
        /// </summary>
        /// <param name="list"></param>
        static void CocktailSort(double[] list) { // the first element of list has index 0
            var bottom = 0;
            var top = list.Length - 1;
            var swapped = true;
            while (swapped == true) {
                // if no elements have been swapped, then the list is sorted
                swapped = false;
                for (int i = bottom ; i < top ; i = i + 1) {
                    if (list[i] > list[i + 1]) {
                        // test whether the two elements are in the correct order
                        Swap(list,i,i + 1); // let the two elements change places
                        swapped = true;
                    }
                }
                // decreases top the because the element with the largest value in the unsorted
                // part of the list is now on the position top 
                top = top - 1;
                for (int i = top ; i > bottom ; i = i - 1) {
                    if (list[i] < list[i - 1]) {
                        Swap(list,i,i - 1);
                        swapped = true;
                    }
                }
                // increases bottom because the element with the smallest value in the unsorted 
                // part of the list is now on the position bottom 
                bottom = bottom + 1;
            }
        }
        #region 归并
        static void MergeSort(double[] data) {
            Merge_Sort(data);
        }
        /// <summary>
        /// 归并排序之归：归并排序入口
        /// </summary>
        /// <param name="data">无序的数组</param>
        /// <returns>有序数组</returns>
        /// <author>Lihua(www.zivsoft.com)</author>
        static double[] Merge_Sort(double[] data) {
            //取数组中间下标
            int middle = data.Length / 2;
            //初始化临时数组let,right，并定义result作为最终有序数组
            double[] left = new double[middle],right = new double[middle],result = new double[data.Length];
            if (data.Length % 2 != 0)//若数组元素奇数个，重新初始化右临时数组
            {
                right = new double[middle + 1];
            }
            if (data.Length <= 1)//只剩下1 or 0个元数，返回，不排序
            {
                return data;
            }
            int i = 0,j = 0;
            foreach (int x in data)//开始排序
            {
                if (i < middle)//填充左数组
                {
                    left[i] = x;
                    i++;
                } else//填充右数组
                {
                    right[j] = x;
                    j++;
                }
            }
            left = Merge_Sort(left);//递归左数组
            right = Merge_Sort(right);//递归右数组
            result = Merge(left,right);//开始排序
            //this.Write(result);//输出排序,测试用(lihua debug)
            return result;
        }
        /// <summary>
        /// 归并排序之并:排序在这一步
        /// </summary>
        /// <param name="a">左数组</param>
        /// <param name="b">右数组</param>
        /// <returns>合并左右数组排序后返回</returns>
        static double[] Merge(double[] a,double[] b) {
            //定义结果数组，用来存储最终结果
            double[] result = new double[a.Length + b.Length];
            int i = 0,j = 0,k = 0;
            while (i < a.Length && j < b.Length) {
                if (a[i] < b[j])//左数组中元素小于右数组中元素
                {
                    result[k++] = a[i++];//将小的那个放到结果数组
                } else//左数组中元素大于右数组中元素
                {
                    result[k++] = b[j++];//将小的那个放到结果数组
                }
            }
            while (i < a.Length)//这里其实是还有左元素，但没有右元素
            {
                result[k++] = a[i++];
            }
            while (j < b.Length)//右右元素，无左元素
            {
                result[k++] = b[j++];
            }
            return result;//返回结果数组
        }
        #endregion
        static void ExtendSort(int[] data) {
            int[] bx = default(int[]);
            int[] ix = default(int[]);
            int len = data.Length;
            int p = default(int);
            while (p < len) {
                ix = new int[p + 1];
                for (int i = 0; i < p; i++) {
                    if (data[p] > bx[i])//总是从最大值处进行比较
                    {
                        ix[i] = data[p];
                        for (int j = i + 1; j < p + 1; j++) {
                            ix[j] = bx[j - 1];
                        }
                        bx = ix;
                        goto there;//若与最大值发生交换,那么其它值进行平移,平移以后跳出,进行下一次数组"膨胀".
                    } else {
                        ix[i] = bx[i];//两个互相依赖的膨胀数组.
                    }
                }
                ix[p] = data[p];//因为膨胀以后光靠原来的依赖数组是无法完全填满数据的,将会留下一个空位,因为数组每次膨胀一个数据位,所以将留有一个数据的空位,而这个空位在完全不发生交换时才由此语句中的右值进行填充.
                bx = ix;//每次数组反灌
            there:
                p++;
            }
            data = bx;
        }
        //
        static public void Sort(int[] data,SortType st = SortType.Insert) {
            switch (st) {
                case SortType.Select:
                SelectSort(data);
                break;
                case SortType.Bubble:
                BubbleSort(data);
                break;
                case SortType.Quick:
                QuickSort(data);
                break;
                case SortType.Insert:
                InsertSort(data);
                break;
                case SortType.OddEven:
                OddEvenSort(data);
                break;
                case SortType.Merge:
                break;
                case SortType.Cocktail:
                CocktailSort(data);
                break;
                case SortType.Extend:
                ExtendSort(data);
                break;
                default:
                break;
            }
        }
        static public void Sort(float[] data,SortType st = SortType.Insert) {
            switch (st) {
                case SortType.Select:
                SelectSort(data);
                break;
                case SortType.Bubble:
                BubbleSort(data);
                break;
                case SortType.Quick:
                QuickSort(data);
                break;
                case SortType.Insert:
                InsertSort(data);
                break;
                case SortType.OddEven:
                OddEvenSort(data);
                break;
                case SortType.Merge:
                break;
                case SortType.Cocktail:
                CocktailSort(data);
                break;
                default:
                break;
            }
        }
        static public void Sort(double[] data,SortType st = SortType.Insert) {
            switch (st) {
                case SortType.Select:
                SelectSort(data);
                break;
                case SortType.Bubble:
                BubbleSort(data);
                break;
                case SortType.Quick:
                QuickSort(data);
                break;
                case SortType.Insert:
                InsertSort(data);
                break;
                case SortType.OddEven:
                OddEvenSort(data);
                break;
                case SortType.Merge:
                MergeSort(data);
                break;
                case SortType.Cocktail:
                CocktailSort(data);
                break;
                default:
                break;
            }
        }
        public enum SortType {
            Select, Bubble, Quick, Insert, OddEven, Merge, Cocktail, Extend
        }
    }
}
